package com.tucc.hello.leetcode.no1_400.no201_400.no279;

import java.util.TreeSet;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        for(int i = 0;i < 100;i ++){
            System.out.println("n: " + i + " " + solution.numSquares(i));
        }
    }

    public int numSquares(int n) {
        int c = 1;
        int c2 = 1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        TreeSet<Integer> squares = new TreeSet<>();
        squares.add(0);
        while (c2 <= n) {
            dp[c2] = 1;
            squares.add(c2);
            c++;
            c2 = c * c;
        }
        for (int i = 1; i <= n; i++) {
            Integer target = squares.floor(i);
            if (target == i) {
                dp[i] = 1;
            } else {
                int min = dp[target] + dp[i - target];
                int s = 1;
                int ss = 1;
                while (ss < target) {
                    min = Math.min(min, dp[ss] + dp[i - ss]);
                    s++;
                    ss = s * s;
                }
                dp[i] = min;
            }
        }
        return dp[n];
    }
}
